package algorthm.systemTraning;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;

/**
 * @className: FindKOccurenceNumber
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/8/24 14:28
 */
public class FindKOccurenceNumber {
//    public static void main(String[] args) {
//       int[] array = { 3 , 3 , 3 , 2 , 2 , 2 , 2 };
//       find(array , 3 , 4);
//    }
    public static int find(int[] array , int k , int m){
        int[] tmp = new int[32];
        for(int i = 0 ; i < array.length ; i++){
            for(int j = 0 ; j < 32 ; j++){
                tmp[j] += ((array[i] & (1<<j)) == 0 ? 0 : 1);
            }
        }
        int rs = 0 ;
        for(int i = 0 ; i < tmp.length ; i++){
            if(tmp[i]%m != 0){
                rs += (1<<i);
            }
        }
        return rs;
    }
    public static int violenceFind(int[] array , int k , int m){
        HashMap<Integer,Integer> map = new HashMap();
        for(Integer i : array){
            if(map.containsKey(i)){
                map.put(i , map.get(i) + 1);
            }else{
                map.put(i , 1);
            }
        }
        for(Integer key : map.keySet()){
            if (map.get(key).equals(k)) {
                return key;
            }
        }
        return -1 ;
    }
    /**
     * @return:
     * @desc: 测试数组的元素个数，每个元素的范围大小，对比的次数
     * @author
     * @date
     * @param
     */
    public static void compareNumber(int numberKind , int range , int compareTimes ){

        for(int ii = 0 ; ii < compareTimes ; ii++ ) {
            // 1. 先找到目标数字，它在数组中出现了
            int k = randomNumber(range) + 1;
            int m = randomNumber(range);
            if (m <= k) {
                m = k + 1;
            }
            int kNum = randomNumber(range) ;
            int mNum = randomNumber(range);
            if(kNum == mNum){
                mNum++;
            }
            int[] testArray = new int[k + m*(numberKind-1)];

            for (int i = 0; i < k; i++) {
                testArray[i] = kNum;
            }
            HashSet<Integer> number = new HashSet<>();
            number.add(kNum);
            number.add(mNum);
            int currNum = randomNumber(range);
            int index = k ;
            for (int i = 0 ; i < numberKind - 1 ; i++){

                while (number.contains(currNum)){
                    currNum = randomNumber(range);
                }
                number.add(currNum);
                int j = 0;
                for( ; j < m; j++){
                    testArray[index + j] = currNum ;
                }
                index += j ;
            }
            int ans = find(testArray, k, m) ;
            int ans1 = violenceFind(testArray, k, m) ;
            if ( ans != ans1 ) {
                System.out.println("存在问题");
                System.out.println("k=" + k + " , m=" + m );
                System.out.println("array:" + Arrays.toString(testArray));
                System.out.println("find resutl:" + ans +" ,violenceFind result: " + ans1);
                return;
            }
        }
    }
    public static int randomNumber(int range){
        return new Random().nextInt(range);
    }

    public static void main(String[] args) {
        compareNumber(190 , 1000 , 100000);
    }
}